package com.linyaonan.leetcode.sword_to_offer._04;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 *  
 *
 * 示例:
 *
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 *
 * 给定 target = 20，返回 false。
 *
 *  
 *
 * 限制：
 *
 * 0 <= n <= 1000
 *
 * 0 <= m <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author: Lin
 * @date: 2022/7/26
 */
public class FindNumberIn2DArray {

    /**
     * 由于横纵均是递增的结构，那么很自然想到的就是二分法查找
     *
     * 第一行的数据就是一列中最小的，那么假如第一行的某位数值大于目标值，那么该列右边的所有列直接排除
     *
     * 同理最后一行数据是这一列中最大的，如果某位数值小于目标值，那么该列左边的所有列直接排除
     *
     * 同理横轴也是一样的思路，最终会框出一个内部二维数组，数值只可能在该范围内
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean f(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }

        int min = matrix[0][0];
        int max = matrix[matrix.length - 1][matrix[0].length - 1];

        // 边界情况
        if (target < min || target > max) {
            return false;
        }

        if (target == min || target == max) {
            return true;
        }

        // 列的最大值
        int n = matrix[0].length - 1;

        // 找到可以进行遍历的最右列
        boolean check = true;
        while (check) {
            int cur = matrix[0][n];
            if (cur == target) {
                return true;
            }
            if (cur > target) {
                n--;
            } else {
                check = false;
            }
        }

        for (int i = n; i >= 0;) {
            for (int j = 0; j < matrix.length;) {
                int p = matrix[j][i];
                System.out.println(p);
                if (p == target) {
                    return true;
                }
                if (p < target) {
                    j++;
                } else {
                    break;
                }
            }
            i--;
        }

        return false;
    }





}
